package Leetcode.Dichotomy;

/**
 * @Author: kirito
 * @Date: 2024/4/2 18:23
 * @Description:
 * 正整数和负整数的最大计数
 * 给你一个按 非递减顺序 排列的数组 nums ，返回正整数数目和负整数数目中的最大值。
 *
 * 换句话讲，如果 nums 中正整数的数目是 pos ，而负整数的数目是 neg ，返回 pos 和 neg二者中的最大值。
 * 注意：0 既不是正整数也不是负整数。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [-2,-1,-1,1,2,3]
 * 输出：3
 * 解释：共有 3 个正整数和 3 个负整数。计数得到的最大值是 3 。
 * 示例 2：
 *
 * 输入：nums = [-3,-2,-1,0,0,1,2]
 * 输出：3
 * 解释：共有 2 个正整数和 3 个负整数。计数得到的最大值是 3 。
 * 示例 3：
 *
 * 输入：nums = [5,20,66,1314]
 * 输出：4
 * 解释：共有 4 个正整数和 0 个负整数。计数得到的最大值是 4 。
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 2000
 * -2000 <= nums[i] <= 2000
 * nums 按 非递减顺序 排列。
 *
 *
 * 进阶：你可以设计并实现时间复杂度为 O(log(n)) 的算法解决此问题吗？
 */

public class maximumCount {
    public static void main(String[] args) {
//        int[] nums = {-1};
//        System.out.println(maximumCount(nums));
        System.out.println(multiply(1,10));
    }

    /**
     * 不用* 去完成乘法，递归乘法
     * @param A
     * @param B
     * @return
     */
    static int multiply(int A, int B){
        int max = Math.max(A,B);
        int min = max ==A? B:A;
        if (min == 0) {
            return 0;
        }
        return max + multiply(min-1,max);
    }
    /**
     * 1.暴力  O(N)
     * 2.二分
     *
     * @param nums
     * @return
     */
    public static int maximumCount(int[] nums) {
        return Math.max(lowerbound(nums, 0), nums.length- lowerbound(nums, 1));
    }
    //闭区间写法，第一个大于等于target的索引
    private static int lowerbound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left <= right) {//区间不为空
            int mid = (left + right) / 2;
            if(nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return left;
    }

    /**
     * 快速幂
     * @param base 底
     * @param exponent 指数
     * @return 结果
     */
    public static long quickPow(int base, int exponent) {
        if (exponent == 0) {
            return 1;
        }
        if (exponent % 2 == 0) {
            long half = quickPow(base, exponent / 2);
            return half * half;
        } else {
            return base * quickPow(base, exponent - 1);
        }
    }

}
